package com.cty.C_SortAlgorithms.A_BubbleSort;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/17 9:13
 * @Description: 冒泡排序  基于数组实现
 * 基本概念：
 *      不变性：
 *          算法在执行的过程中存在一些一直成立的条件，可以用来验证算法是否出现错误。
 *      稳定性：
 *          排序时出现相同关键字，排序并不影响这些具有相同关键字的数据的顺序。
 * 排序算法选择：
 *      数据随机分布时【1】
 *          数据量【2】小时（如 N ≤ 50），考虑简单排序方法（若要求稳定性【3】，只能使用“插入排序”）
 *              首选“插入排序”，若效率差可升级为“希尔排序” 【4 时间和空间的选择】
 *              移动远比比较耗时时，可使用“选择排序”——交换次数少
 *          数据量大时，考虑使用时间复杂度为 O(N*logN) 的排序算法
 *              首选“快速排序”——时间效率最高
 *              若对空间要求严格，可使用“堆排序”——空间效率最高
 *              若要求稳定性且空间充足，可使用“归并排序”——具有稳定性
 *
 *      数据基本逆序时
 *          数据量小时，同数据随机分布时情况
 *          数据量大时，建议使用“堆排序”
 *
 *      数据基本有序时
 *          可使用“冒泡排序”、“插入排序”和“快速排序”，建议使用“插入排序”
 *
 *     另外，数据位数小或其他进制数排序时，可考虑使用“基数排序”
 * @version: 1.0
 */
public class BubbleSort {
    private int maxSize;
    private DataItem[] array;
    private int nItems;

    public BubbleSort(int maxSize){
        this.maxSize = maxSize;
        array = new DataItem[maxSize];
        nItems = 0;
    }

    public boolean isEmpty(){
        return (nItems == 0);
    }

    public boolean isFull(){
        return (nItems == maxSize);
    }

    public int size(){
        return nItems;
    }

    public void displayArray(){
        for(int i=0; i<nItems; i++)
            System.out.print(array[i].getKey() + " ");
        System.out.println();
    }

    /**
     * 数组尾部插入数据  O(1)
     * @param item
     * @return
     */
    public boolean insert(DataItem item){
        if(isFull())
            return false;

        array[nItems++] = item;
        return true;
    }

    /**
     * 冒泡排序
     *      平均时间复杂度：  O(N^2)    数据随机分布    s = 比较次数 + 交换次数 = N*(N-1)/2 + N*(N-1)/4    交换的次数平均来说是比较的一半
     *      最好情况：        O(N)      数据顺序分布    s = 比较次数 + 交换次数 = N + 0 = N
     *      最坏情况：       O(N^2)     数据逆序分布    s = 比较次数 + 交换次数 = N*(N-1)/2 + N*(N-1)/2    每次比较都需要交换
     *      空间复杂度：      O(1)      不需要额外空间辅助
     *      排序方式：                  内部排序
     *      稳定性：                    稳定
     */
    public void bubbleSort(){
        boolean didSwap;
        int in, out;
        for(out=nItems-1; out>0; out--) {  // >0 而不是 >=0，是因为只剩下最后一个数据项时，不用再遍历排序，它一定关键字最小
            didSwap = false;
            for (in = 0; in < out; in++)  // out 位置处尚未排序
                if (array[in].getKey() > array[in + 1].getKey()) {  // 比较  > 保证了稳定性
                    // 交换
                    DataItem temp = array[in].getItem();
                    array[in].setItem(array[in + 1]);
                    array[in + 1].setItem(temp);
                    didSwap = true;
                }
            if(!didSwap)
                return;
        }
    }  // end bubbleSort()














    // 练习 冒泡排序


}  // end BubbleSort{}
